package mo.leetcode_top;

import java.util.*;

public class L524 {

    public String findLongestWord(String s, List<String> dictionary) {
        int[] chars = new int[26];
        char[] charArray = s.toCharArray();
        for (char c : charArray) {
            chars[c-'a']++;
        }
        List<String> candidate = new ArrayList<>();
        for (String d : dictionary) {
            int[] copy = Arrays.copyOf(chars, 26);
            for (char cr : d.toCharArray()) {
                if (copy[cr-'a'] == 0) {
                    break;
                } else {
                    copy[cr-'a']--;
                }
            }
            candidate.add(d);
        }

        List<String> res = new ArrayList<>();
        int max = 0;
        for (String c : candidate) {
            char[] current = c.toCharArray();
            int index = 0;
            int satisfy = 0;
            for (int i = 0; i < current.length; i++) {
                while (index < charArray.length) {
                    if (charArray[index] == current[i]) {
                        index++;
                        satisfy++;
                        break;
                    }
                    index++;
                }
            }
            if (satisfy == current.length) {
                if (satisfy > max) {
                    res.clear();
                    res.add(c);
                    max = satisfy;
                } else if (satisfy == max) {
                    res.add(c);
                }
            }
        }

        if (res.size() == 0) {
            return "";
        } else {
            res.sort(String::compareTo);
            return res.get(0);
        }
    }


    public String findLongestWord2(String s, List<String> dictionary) {
        dictionary.sort((o1, o2) -> {
            if (o1.length() != o2.length()) {
                return o2.length() - o1.length();
            } else {
                return o1.compareTo(o2);
            }
        });

        char[] charArray = s.toCharArray();
        for (String c : dictionary) {
            char[] current = c.toCharArray();
            int index = 0;
            int satisfy = 0;
            for (int i = 0; i < current.length; i++) {
                while (index < charArray.length) {
                    if (charArray[index] == current[i]) {
                        index++;
                        satisfy++;
                        break;
                    }
                    index++;
                }
            }
            if (satisfy == current.length) {
                return c;
            }
        }

        return "";
    }



    public static void main(String[] args) {
        L524 test = new L524();
        System.out.println(test.findLongestWord("aaa", Arrays.asList("aaa", "aa", "a")));
    }
}
